/*
https://leetcode.cn/problems/longest-increasing-subsequence/
300. 最长递增子序列
medium, 彭珵 2024.9.2
*/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> a;

        for (int i : nums) {
            
            auto it = lower_bound(a.begin(), a.end(), i);

            if (it == a.end()) {
                a.push_back(i); 
            } else {
                *it = i;
            }
        }

        return a.size();
    }
};